package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

/**
 * 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution98 {
    public boolean isValidBST(TreeNode root) {

        return isValidBST(root,null,null);
    }

    /**
     * 限制 根节点左边的数据一定小于根节点 根节点右边的数据一定大于根节点
     *
     * @param root
     * @param min
     * @param max
     * @return
     */
    private boolean isValidBST(TreeNode root,TreeNode min,TreeNode max) {
        if (root == null) {
            return true;
        }
        // 判断 左节点 的顺序
        if (min !=null && root.val <= min.val) {
            return false;
        }
        if (max !=null && root.val >= max.val) {
            return false;
        }

        return  isValidBST(root.left,min,root) && isValidBST(root.right,root,max);
    }

}
